#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

int lengthOfLongestSubsequence(vector<int>& nums, int target) {
    vector<int> f(target + 1, INT_MIN);
    f[0] = 0;
    for (int i = 0; i < nums.size(); i++)
        for (int j = target; j >= nums[i]; j--)
            f[j] = max(f[j], f[j - nums[i]] + 1);
    return f[target] > 0 ? f[target] : -1;
}

int numberOfWays(int n, int x) {
    vector<int> f(n + 1);
    const int mod = 1e9 + 7;
    f[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        long long t = pow(i, x);
        for (int j = n; j >= t; j--)
            f[j] = (f[j] + f[j - t]) % mod;
    }
    return f[n];
}